NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/6481

Internet Message Format | 1996-08-05 | 2.7 KB

Path: keats.ugrad.cs.ubc.ca!not-for-mail
From: [e-mail] (Kazimir Kylheku)
Newsgroups: comp.lang.c
Subject: Re: Does C have Dictionarys like smalltalk does?
Date: 24 Feb 1996 12:20:11 -0800
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Message-ID: <[e-mail]>
References: <4ged8d$[e-mail]>
NNTP-Posting-Host: keats.ugrad.cs.ubc.ca

In article <4ged8d$[e-mail]>,
Andrew Belo <[e-mail]> wrote:
>
>I am trying to make a program that takes a name and phone number and
>"links" them together and stores the name, number and link in a file.  In
>smalltalk I would be able to use a dictionary that associates 2 objects
>together I was wondering if there were similar structures in C.  My

C is not "that kind of language". Dictionaries are typically  not found in
machine language instruction sets.

C is the kind of language in which a Smalltalk compiler or interpreter is
likely to be written.

In C, you can create dictionary data structures yourself. Typically, a
dictionary will be abstracted as the address of a ``struct''---a record which
contains information about that dictionary. What is inside this structure is up
to you. It could be the header record for maintaining a binary tree, hash
table, B+Tree---what have you.

The best way is to implement abstract operations in terms of C functions which
create and destroy dictionaries, insert and delete entries and so forth. C does
not directly support polymorphism, so you can't neatly write a data structure
that will hold objects of any type. One way to do it is to have the structure
hold "void pointers", which are generic addresses. The address of any object
regardless of its type can be converted to such a pointer and back.
You can also define "unions",  which are structures that hold muliple fields in
the same space, much like Pascal "variant records". If you make your dictionary
store objects that are unions of a void pointer and an integer, then you can
directly store pointers to any object in your data structure, as well as
integers.



If you want a quick and dirty (albeit a little limited) dictionary facility
using only ANSI standard C library functions, you can use arrays. The C library
provides a function that can sort arrays which contain elements of arbitrary
types --- you just provide a comparison function which tells qsort() whether
one element is greater than another in terms of some ordering criteria.
Another function, bsearch() implements a binary search on a sorted array.
These two, along with some dynamic array manipulation, can be used to manage
dictionaries of any size. Of course, insertions and deletions are O(n).
Hash tables are much better for this purpose.


--